#include<iostream>
#include<vector>
using namespace std;

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0;
    int right = 0;

    int lenth = 0x3f3f3f3f;
    int m = nums.size();
    int sum = nums[left];
    while (right < m)
    {
        if (right < m && sum < target)
        {
            right++;
            if(right < m)
            sum += nums[right];
        }
        else if (right < m && sum >= target)
        {
            if (right - left < lenth)
            {
                lenth = right - left + 1;
            }
            sum -= nums[left];
            left++;
        }


    }
    return  lenth == 0x3f3f3f3f ? 0 : lenth;


















}
int main()
{

    vector<int>res = { 1,1,1,1,1,1,1,1 };
   int m= minSubArrayLen(11, res);


}
class Solution {
public:
    int maxArea(vector<int>& height) {
        int right = height.size() - 1;
        int left = 0;
        int v = 0;
        while (left != right)
        {
            int minlenth = min(height[left], height[right]);
            v = max(minlenth * (right - left), v);
            if (minlenth == height[left])
                left++;
            else
                right--;
        }
        return v;









    }
}; class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int m = nums.size();
        int sum = 0;
        for (int i = m - 1; i >= 2; i--)
        {
            int right = i - 1, left = 0;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    sum += right - left;
                    right--;
                }
                else
                {
                    left++;
                }




            }

        }
        return sum;








    }
}; class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int m = nums.size();
        vector<int>result;
        vector<int>path;
        for (int i = 0; i < m; i++)
        {
            result.push_back(i);
        }
        sort(result.begin(), result.end(), [nums, result](int i, int j)
            {return nums[result[i]] < nums[result[j]]; });
        int left = 0;
        int right = m - 1;
        while (right < m)
        {
            if (nums[result[left]] + nums[result[right]] > target)
            {
                right--;

            }
            else if (nums[result[left]] + nums[result[right]] < target)
            {
                left++;
            }
            else
            {
                path.push_back(result[left]);
                path.push_back(result[right]);
                break;
            }
        }
        return path;







    }
}; class Solution {
public:
    vector<int> twoSum(vector<int>& array, int sum) {
        int m = array.size();
        int left = 0;
        int right = m - 1;
        vector<int>result;
        int target = array[left] + array[right];
        while (left < right)
        {
            if (target > sum)
            {
                target -= array[right];
                right--;
                target += array[right];
            }
            else if (target < sum)
            {

                target -= array[left];
                left++;
                target += array[left];
            }
            else {
                result.push_back(left + 1);
                result.push_back(right + 1);
                break;

            }








        }
        return result;
    }
}; class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>result;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n;)
        {
            if (nums[i] > 0)break;
            int left = i + 1, right = n - 1; int target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target)
                {
                    right--;
                }
                else if (sum < target)
                {
                    left++;
                }
                else
                {
                    result.push_back({ nums[i],nums[left],nums[right] });
                    left++;
                    right--;
                    while (left < right & nums[left] == nums[left - 1])left++;
                    while (left < right && nums[right] == nums[right + 1])right--;
                }

            }
            i++;
            while (i < n && nums[i] == nums[i - 1])i++;
        }
        return result;
    }
}; class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>>result;
        sort(nums.begin(), nums.end());
        int m = nums.size();
        for (int i = 0; i < m;)
        {
            for (int j = i + 1; j < m;)
            {
                int left = j + 1, right = m - 1; long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum > aim)
                    {
                        right--;
                    }
                    else if (sum < aim)
                    {
                        left++;
                    }
                    else
                    {
                        result.push_back({ nums[i],nums[j],nums[left],nums[right] });
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1])left++;
                        while (left < right && nums[right] == nums[right + 1])right--;

                    }
                }
                j++;
                while (j < m && nums[j] == nums[j - 1])j++;




            }
            i++;
            while (i < m && nums[i] == nums[i - 1])i++;
        }


        return result;

    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int>result;
    void inorder(TreeNode* root)
    {
        if (root == nullptr)
            return;
        inorder(root->left);
        result.push_back(root->val);
        inorder(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        inorder(root);
        return result[k - 1];
    }
};/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p && p == q)
            return root;
        TreeNode* cur = root;
        while (cur)
        {
            if (cur->val > p->val && cur->val > q->val)
            {
                cur = cur->left;
            }
            else if (cur->val < p->val && cur->val < q->val)
            {
                cur = cur->right;
            }
            else
            {
                return cur;
            }





        }
        return nullptr;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)return nullptr;
        if (root == p || root == q)return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr)return root;
        if (left != nullptr && right == nullptr)return left;
        if (left == nullptr && right != nullptr)return right;
        return nullptr;
    }
};